package sol.leetcode;

/**
 * Populating Next Right Pointers in Each Node
 */
public class Issue116 {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;

        connect(root.left);
        connect(root.right);
        TreeLinkNode l = root.left;
        TreeLinkNode r = root.right;
        while (null != l && null != r) {
            l.next = r;
            l = l.right;
            r = r.left;
        }
    }

    public static void main(String[] args) {
        TreeLinkNode node1 = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node7 = new TreeLinkNode(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        Issue116 sol = new Issue116();
        sol.connect(node7);

        System.out.println("Done!");
    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;

    TreeLinkNode(int x) {
        val = x;
    }
}
